#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "quicksort.h"


// Estrutura de uma árvore binária
typedef struct stt_tree {
    int *local;
    struct stt_tree *filho_esq;
    struct stt_tree *filho_dir;
} arvore_b;


// Função principal que constrói uma KD Tree
arvore_b *kdtree(int **p, int profundidade, int n_pontos, int k) {
    
    int i, j;
    
    if (!p[0])
        return NULL;
    
    // Selecionando o eixo baseado na profundade tal que o eixo circule em
    // torno de todos os valores válidos.
    int eixo;
    eixo = profundidade % k;
    
    // Ordena a lista de pontos
    quick_sort(p, 0, n_pontos-1, eixo);
    
    // Escolhe o ponto medio como o elemento pivo
    int meio;
    meio = n_pontos / 2;
    
    // Determina pontos que vão à direita e à esquerda da árvore
    int **pontos_esq;
    int **pontos_dir;
    pontos_esq = malloc(sizeof(int*) * meio+1);
    pontos_dir = malloc(sizeof(int*) * (n_pontos-meio+1));
    
    // Gera uma nova lista de pontos que irão a esquerda e direita da sub-árvore
    i = 0;
    while (i < meio) {
        pontos_esq[i] = malloc(sizeof(int) * k);
        memcpy(pontos_esq[i], p[i], sizeof(int) * k);
        i++;
    }
    pontos_esq[i] = NULL;
    
    i = 0;
    while (i < n_pontos-meio-1) {
        pontos_dir[i] = malloc(sizeof(int*) * k);
        memcpy(pontos_dir[i], p[i+meio+1], sizeof(int) * k);
        i++;
    }
    pontos_dir[i] = NULL;
    
    // Cria o no e constrói as sub-árvores
    arvore_b *no;
    no = (arvore_b*) malloc(sizeof(arvore_b));
    
    int *valor_meio = malloc(sizeof(int) * k);
    memcpy(valor_meio, p[meio], sizeof(int) * k);
    no->local = valor_meio;
    
    for(i = 0; i < n_pontos-1; i++)
        free(p[i]);
    free(p);
    
    no->filho_esq = kdtree(pontos_esq, profundidade+1, meio, k);
    no->filho_dir = kdtree(pontos_dir, profundidade+1, n_pontos-meio-1, k);
    
    return no;
}


void main(int argc, char *argv[]) {
    
    FILE *arquivo;
    int **pontos;
    int k = atoi(argv[2]);          // Tamanho da dimensão
    int n_pontos = atoi(argv[3]);   // Número de pontos retirados do arquivo
    
    // Abrindo arquivo de entrada
    arquivo = fopen(argv[1], "r");
    if (!arquivo) {
        printf("Não foi possível abrir o arquivo\n");
        return;
    } else {
        // Alocando memória Para o vetor de vetores de k dimensões
        pontos = malloc(sizeof(int*) * n_pontos + 1);
    }
    
    // Lendo cada linha da entrada e atribuindo os valores
    int ponto[k], i, j;
    for (i=0; i<n_pontos; i++) {
        for(j=0; j < k-1; j++)
            fscanf(arquivo, "%d ", &ponto[j]);
        fscanf(arquivo, "%d", &ponto[j]);
        pontos[i] = malloc(sizeof(int) * k);
        for (j=0; j<k; j++) 
            pontos[i][j] = ponto[j];
    }
    pontos[i] = NULL;
    
    arvore_b *t;
    t = (arvore_b*) malloc(sizeof(arvore_b));
    
    // Inicia programa computação do problema
    t = kdtree(pontos, 0, n_pontos, k);
    
    printf("(%d, %d, %d)\n", t->local[0], t->local[1], t->local[2]);
    printf("(%d, %d, %d)\n", t->filho_dir->local[0], t->filho_dir->local[1], t->filho_dir->local[2]);
    printf("(%d, %d, %d)\n", t->filho_esq->local[0], t->filho_esq->local[1], t->filho_esq->local[2]);
}